//回溯算法

/** 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 * 递归、回溯、剪枝；时间复杂度: O(n * 2^n)，空间复杂度: O(n)
 * @param n 1 ... n 的整数
 * @param k 数组的长度，递归的深度；
 * @returns 二维数组
 */
export function combine(n: number, k: number): number[][] {
  let resArr: number[][] = [];
  function backTracking(
    n: number,
    k: number,
    startIndex: number,
    tempArr: number[]
  ): void {
    if (tempArr.length === k) {
      resArr.push(tempArr.slice()); //浅复制
      return;
    }
    //剪枝优化；实际上是缩小范围；
    for (let i = startIndex; i <= n - k + 1 + tempArr.length; i++) {
      tempArr.push(i);
      //递归
      backTracking(n, k, i + 1, tempArr);
      tempArr.pop(); //回溯
    }
  }
  backTracking(n, k, 1, []);
  return resArr;
}

/** 电话号码组合
 *
 * @param digits 数字键盘
 * @returns
 */
export function letterCombinations(digits: string): string[] {
  if (digits === "") return [];
  const strMap: { [index: string]: string[] } = {
    1: [],
    2: ["a", "b", "c"],
    3: ["d", "e", "f"],
    4: ["g", "h", "i"],
    5: ["j", "k", "l"],
    6: ["m", "n", "o"],
    7: ["p", "q", "r", "s"],
    8: ["t", "u", "v"],
    9: ["w", "x", "y", "z"],
  };
  const resArr: string[] = [];
  function backTracking(
    digits: string,
    curIndex: number,
    route: string[]
  ): void {
    if (curIndex === digits.length) {
      resArr.push(route.join(""));
      return;
    }
    let tempArr: string[] = strMap[digits[curIndex]];
    for (let i = 0, length = tempArr.length; i < length; i++) {
      route.push(tempArr[i]);
      backTracking(digits, curIndex + 1, route);
      route.pop();
    }
  }
  backTracking(digits, 0, []);
  return resArr;
}

/** 分割回文串;
 * 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
 * 返回 s 所有可能的分割方案。
 * @param s 字符串
 * @returns string[][]
 */
export function partition(s: string): string[][] {
  const res: string[][] = [];
  const path: string[] = [];
  /** 字符串通过始终下标位置判断是否为回文子串；
   * 双指针搜索法；
   * @param str 字符串
   * @param startIndex 起始下标
   * @param endIndex 终止下标
   * @returns boolean
   */
  const isHuiwen = (
    str: string,
    startIndex: number,
    endIndex: number
  ): boolean => {
    for (; startIndex < endIndex; startIndex++, endIndex--) {
      if (str[startIndex] !== str[endIndex]) {
        return false;
      }
    }
    return true;
  };

  const rec = (str: string, index: number): void => {
    if (index >= str.length) {
      res.push([...path]);
      return;
    }
    for (let i = 0; i < str.length; i++) {
      if (!isHuiwen(str, index, i)) {
        continue;
      }
      path.push(str.substring(index, i + 1));
      rec(str, i + 1);
      path.pop();
    }
  };
  rec(s, 0);
  return res;
}

/** 是否为有效的ip片段
 *
 * @param str
 * @returns boolean
 */
function isValidIpSegment(str: string): boolean {
  let resBool: boolean = true;
  let tempVal: number = Number(str);
  if (
    str.length === 0 ||
    isNaN(tempVal) ||
    tempVal > 255 ||
    tempVal < 0 ||
    (str.length > 1 && str[0] === "0")
  ) {
    resBool = false;
  }
  return resBool;
}

/** 复原IP地址
 * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
 * @param s 数字字符串
 * @returns string[]
 */
export function restoreIpAddresses(s: string): string[] {
  const resArr: string[] = [];
  backTracking(s, 0, []);
  return resArr;
  function backTracking(s: string, startIndex: number, route: string[]): void {
    let length: number = s.length;
    if (route.length === 4 && startIndex >= length) {
      resArr.push(route.join("."));
      return;
    }
    if (route.length === 4 || startIndex >= length) return;
    let tempStr: string = "";
    for (let i = startIndex + 1; i <= Math.min(length, startIndex + 3); i++) {
      tempStr = s.slice(startIndex, i);
      if (isValidIpSegment(tempStr)) {
        route.push(s.slice(startIndex, i));
        backTracking(s, i, route);
        route.pop();
      }
    }
  }
}

/** 子集
 * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 * @param nums
 * @returns
 */
export function subsets(nums: number[]): number[][] {
  const resArr: number[][] = [];
  backTracking(nums, 0, []);
  return resArr;
  function backTracking(
    nums: number[],
    startIndex: number,
    route: number[]
  ): void {
    resArr.push([...route]);
    let length = nums.length;
    if (startIndex === length) return;
    for (let i = startIndex; i < length; i++) {
      route.push(nums[i]);
      backTracking(nums, i + 1, route);
      route.pop();
    }
  }
}

/** 子集II
 * 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 * @param nums
 * @returns
 */
export function subsetsWithDup(nums: number[]): number[][] {
  nums.sort((a, b) => a - b); //递增排序
  const resArr: number[][] = [];
  backTraking(nums, 0, []);
  return resArr;
  function backTraking(
    nums: number[],
    startIndex: number,
    route: number[]
  ): void {
    resArr.push([...route]);
    let length: number = nums.length;
    if (startIndex === length) return;
    for (let i = startIndex; i < length; i++) {
      if (i > startIndex && nums[i] === nums[i - 1]) continue; //树层去重
      route.push(nums[i]);
      backTraking(nums, i + 1, route);
      route.pop();
    }
  }
}

/** 递增子序列
 * 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
 * @param nums
 * @returns
 */
export function findSubsequences(nums: number[]): number[][] {
  const resArr: number[][] = [];
  // 回溯法搜索
  backTracking(nums, 0, []);
  // 返回路径数组
  return resArr;
  // 回溯法搜索函数
  function backTracking(
    nums: number[],
    startIndex: number,
    route: number[]
  ): void {
    // 获取数组长度
    let length: number = nums.length;
    // 如果路径数组长度大于等于2，则将路径数组添加到结果数组中
    if (route.length >= 2) {
      resArr.push(route.slice());
    }
    // 创建一个Set集合
    const usedSet: Set<number> = new Set();
    // 遍历数组
    for (let i = startIndex; i < length; i++) {
      // 如果当前元素小于路径数组最后一个元素或者已经使用过，则跳过
      if (nums[i] < route[route.length - 1] || usedSet.has(nums[i])) continue;
      // 将当前元素添加到Set集合中
      usedSet.add(nums[i]);
      // 将当前元素添加到路径数组中
      route.push(nums[i]);
      // 递归调用回溯法搜索函数
      backTracking(nums, i + 1, route);
      // 将当前元素从路径数组中移除
      route.pop();
    }
  }
}

//#region 求和组合，回溯算法
/** 给定一个无重复元素的数组 candidates 和一个目标数 target 。
 * 找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的数字可以无限制重复被选取。
 * @param candidates  中的数字可以无限制重复被选取。
 * @param target 目标数 target
 * @returns
 */
export function combinationSum(
  candidates: number[],
  target: number
): number[][] {
  /** 结果二维数组
   *
   */
  const resArr: number[][] = [];

  /** 回溯递归
   *
   * @param candidates 候选人数组
   * @param target 目标和
   * @param startIndex 起始下标
   * @param route 路径数组
   * @param curSum 当前和
   * @returns void
   */
  function backTracking(
    candidates: number[],
    target: number,
    startIndex: number,
    route: number[],
    curSum: number
  ): void {
    if (curSum > target) return;
    if (curSum === target) {
      resArr.push(route.slice());
      return;
    }
    for (let i = startIndex, length = candidates.length; i < length; i++) {
      let tempVal: number = candidates[i];
      route.push(tempVal);
      backTracking(candidates, target, i, route, curSum + tempVal);
      route.pop();
    }
  }
  backTracking(candidates, target, 0, [], 0);
  return resArr;
}

/** 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用一次。
 * 回溯递归，输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * @param candidates 候选人数组，有重复项，
 * @param target 目标和
 * @returns
 */
export function combinationSum2(
  candidates: number[],
  target: number
): number[][] {
  candidates.sort((a, b) => a - b);
  const resArr: number[][] = [];
  /**
   *
   * @param candidates 候选人数组
   * @param target 目标和
   * @param curSum 当前和
   * @param startIndex 起始下标
   * @param route 路径数组
   * @returns
   */
  function backTracking(
    candidates: number[],
    target: number,
    curSum: number,
    startIndex: number,
    route: number[]
  ) {
    if (curSum > target) return;
    if (curSum === target) {
      resArr.push(route.slice());
      return;
    }
    for (let i = startIndex, length = candidates.length; i < length; i++) {
      if (i > startIndex && candidates[i] === candidates[i - 1]) {
        continue;
      }
      let tempVal: number = candidates[i];
      route.push(tempVal);
      backTracking(candidates, target, curSum + tempVal, i + 1, route);
      route.pop();
    }
  }
  backTracking(candidates, target, 0, 0, []);
  return resArr;
}

/** 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复。
 *
 * @param k 组合数
 * @param n 目标和
 * @returns 符合的二维数组
 */
export function combinationSum3(k: number, n: number): number[][] {
  const resArr: number[][] = [];
  function backTracking(
    k: number,
    n: number,
    sum: number,
    startIndex: number,
    tempArr: number[]
  ): void {
    if (sum > n) return;
    if (tempArr.length === k) {
      if (sum === n) {
        resArr.push(tempArr.slice());
      }
      return;
    }
    for (let i = startIndex; i <= 9 - (k - tempArr.length) + 1; i++) {
      tempArr.push(i);
      backTracking(k, n, sum + i, i + 1, tempArr);
      tempArr.pop();
    }
  }
  backTracking(k, n, 0, 1, []);
  return resArr;
}
//#endregion

/** 是否有效
 *
 * @param col
 * @param row
 * @param val
 * @param board
 * @returns
 */
function isValid(
  col: number,
  row: number,
  val: string,
  board: string[][]
): boolean {
  let n: number = board.length;
  // 列向检查
  for (let rowIndex = 0; rowIndex < n; rowIndex++) {
    if (board[rowIndex][col] === val) return false;
  }
  // 横向检查
  for (let colIndex = 0; colIndex < n; colIndex++) {
    if (board[row][colIndex] === val) return false;
  }
  // 九宫格检查
  const startX = Math.floor(col / 3) * 3;
  const startY = Math.floor(row / 3) * 3;
  for (let rowIndex = startY; rowIndex < startY + 3; rowIndex++) {
    for (let colIndex = startX; colIndex < startX + 3; colIndex++) {
      if (board[rowIndex][colIndex] === val) return false;
    }
  }
  return true;
}

/** 解数独
 *
 * @param board
 */
export function solveSudoku(board: string[][]): string[][] {
  let n: number = 9;
  backTracking(n, board);
  function backTracking(n: number, board: string[][]): boolean {
    for (let row = 0; row < n; row++) {
      for (let col = 0; col < n; col++) {
        if (board[row][col] === ".") {
          for (let i = 1; i <= n; i++) {
            if (isValid(col, row, String(i), board)) {
              board[row][col] = String(i);
              if (backTracking(n, board) === true) return true;
              board[row][col] = ".";
            }
          }
          return false;
        }
      }
    }
    return true;
  }
  return board;
}
